package com.kingwood.algorithm.test;

import java.util.Scanner;

public class SanChaShu {
    static class TreeNode {
         int val;
         int height;
         TreeNode left;
         TreeNode mid;
         TreeNode right;

         public TreeNode (int val) {
             this.val = val;
         }
    }

    /**
     * https://fcqian.blog.csdn.net/article/details/134709517
     * 计算三叉搜索树的高度
     */
    static class Tree {
        TreeNode root;
        int height;

        public void add(int val) {
            TreeNode treeNode = new TreeNode(val);

            if (root == null) {
                this.height = 1;
                this.root = treeNode;
                treeNode.height = 1;
            } else {
                TreeNode cur = this.root;
                while (true) {
                    treeNode.height = cur.height + 1;
                    this.height = Math.max(this.height, treeNode.height);

                    if (val < cur.val - 500) {
                        if (cur.left == null) {
                            cur.left = treeNode;
                            break;
                        } else {
                            cur = cur.left;
                        }
                    } else if (val > cur.val + 500) {
                        if (cur.right == null) {
                            cur.right = treeNode;
                            break;
                        } else {
                            cur  = cur.right;
                        }
                    } else {
                        if (cur.mid == null) {
                            cur.mid = treeNode;
                            break;
                        } else {
                            cur = cur.mid;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            try {
                int n = scanner.nextInt();
                Tree tree = new Tree();

                for (int i=0; i<n; i++) {
                    int num = scanner.nextInt();
                    tree.add(num);
                }

                System.out.println(tree.height);
                break;
            } catch (Exception e) {
                break;
            }
        }
    }
}
